package algorithms.leecode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Au68 {
    public static void main(String[] args) {
        String[] strings = new String[]{
                "ask","not","what","your","country","can","do","for","you","ask","what","you","can","do","for","your","country"

        };
        List<String> s = new Au68().fullJustify(strings,16);
        s.forEach((item)-> System.err.println(item.length()));
    }
    public List<String> fullJustify(String[] words, int maxWidth) {
        Queue<String> queue = new LinkedList<>();
        List<String> list = new ArrayList<>();
        int length = 0;
        for (int i = 0; i < words.length; i++) {
            int len = words[i].length();
            if (length + len + queue.size()> maxWidth) {
                int des = maxWidth - length;
                int size = queue.size();
                int n = size > 1 ?des / (size - 1) : des;
                int l = size > 1 ? des % (size - 1) : 0;
                int count = size > 1 ? size - 1 : 1;
                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < size; j++) {
                    String s = queue.poll();
                    builder.append(s);
                    int el = n;
                    if(l > 0) {
                        l--;
                        el++;
                    }
                    for (int k = 0; k < el && j < count; k++) {
                        builder.append(" ");
                    }
                }
                list.add(builder.toString());
                length = 0;
            }
            queue.add(words[i]);
            length += len;
            if (i == words.length - 1) {
                int size = queue.size();
                StringBuilder builder = new StringBuilder();
                for (int i1 = 0; i1 < size; i1++) {
                    builder.append(queue.poll());
                    if (maxWidth > builder.length()) {
                        builder.append(" ");
                    }
                }
                int len1 = builder.length();
                int less = maxWidth - len1;
                for (int i1 = 0; i1 < less; i1++) {
                    builder.append(" ");
                }
                list.add(builder.toString());
            }
        }
        return list;
    }
}
